1. Field of the Invention
The invention relates to digital communication systems, and more particularly to branch metric computation and add-compare-select operation in Viterbi decoders.
2. Description of the Related Art
In wired and wireless applications, especially wireless LAN (WLAN), finite signal and noise powers lead to a strong probability that any bit in any message may be corrupted. These corrupted bits incur errors in wireless transmission, causing troubles like lower data rates or lost transmissions. Forward error correction (FEC) techniques have been developed to account and correct for corrupted bits. The purpose of FEC is to improve the capacity of a channel by adding some carefully designed redundant information to the data being transmitted through the channel. The process of adding this redundant information is known as channel coding. Convolutional coding and block coding are two major forms of channel coding. Convolutional codes operate on a continuous input stream, one or a few bits at a time, which offer an alternative to block codes for transmission over a noisy channel.
A convolutional encoder is a Mealy machine, where the output is a function of the current machine state and the current input. In general, convolutional codes are described by two parameters: the coding rate and the constraint length. The coding rate, k/n, is expressed as a ratio of the number of bits into the convolutional encoder (k) to the number of channel symbols output by the convolutional encoder (n) in a given encoder cycle. The constraint length, K, denotes the “length” of the convolutional encoder, i.e., how many k-bit stages are available to feed the combinational logic that produces the output symbols.
In 1967, Andrew J. Viterbi introduced a decoding algorithm for convolutional codes which has become known as the Viterbi algorithm. The Viterbi algorithm is defined in terms of a graph which is called a trellis diagram. A trellis diagram is a 2-dimensional array of nodes that are connected with arcs, namely branches. Each column in the array contains 2K−1 nodes which represent the 2K−1 states of the convolutional encoder. In each stage of the encoding procedure, the encoder receives a k-bit symbol, outputs an n-bit symbol based on its current state and the input symbol, and enters a new state which is a function of its current state and the input symbol. An arc in the trellis diagram from row p in column i to row u in column i+1 corresponds to the encoder going from state p at instant i of the encoding procedure to state u at instant i+1. When applied to a sequence of symbols received from a memory-less channel, in an iterative manner, the Viterbi algorithm finds the maximum likelihood path through the trellis diagram and thereby outputs the decoded data.
Viterbi decoding has been the subject of several U.S. patents including U.S. Pat. No. 5,878,060, U.S. Pat. No. 5,912,908, and U.S. Pat. No. 6,415,415. An advantage of the Viterbi decoding is the fixed decoding time. The Viterbi algorithm is well suited to hardware decoder implementation, but its computational requirements grow exponentially as a function of the constraint length. Traditionally, performance and silicon area are the two most important concerns in VLSI design. In recent years, power dissipation has also become an important concern, especially in battery-powered applications, such as cellular phones, laptop computers, and WLAN adapters. Compared with a K=5 convolutional code for use in GSM systems, the convolutional code specified in the IEEE 802.11a/g standard has a constraint length of K=7. As the constraint length increases, the decoding process in the receiver becomes increasingly complicated and consumes more power. Several studies have shown that the Viterbi decoder consumes more than one-third of the chip area and the power dissipation of the baseband modem. Consequently, it is necessary to address the issues of low-power design for the Viterbi decoder.